package com.example.jianzhioffer;

/**
 * Created by Quincy on 2018/9/15.
 * 题目描述
 * 请实现两个函数，分别用来序列化和反序列化二叉树。
 * 分析
 * 如果二叉树的序列化是从根节点开始，那么对应的而反序列化也是从根节点开始的。因此可以使用二叉树的前序遍历来序列化二叉树，
 * 当前序遍历碰到null值是，使用“#”表示，每一个节点的数值之间用“，”隔开。
 */
public class DSerializeTree {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public int index = -1; // 节点在序列中的索引

    /**
     * 序列化
     * 前序遍历，将二叉树节点的值转为字符序列，null转为“#”
     */
    String Serialize(TreeNode root){
        StringBuffer s = new StringBuffer();
        if (root == null){
            s.append("#,");
            return s.toString();
        }
        s.append(root.val + ",");
        s.append(Serialize(root.left));
        s.append(Serialize(root.right));
        return s.toString();
    }
/**
 * 反序列化
 * */
    TreeNode Deserialize(String str){
        index++;
        int length = str.length();
        if (index >= length){
            return null;
        }
        String[] nodeSeq = str.split(",");
        TreeNode pNode = null;
        if (!nodeSeq[index].equals("#")){
            pNode = new TreeNode(Integer.valueOf(nodeSeq[index]));
            pNode.left = Deserialize(str);
            pNode.right = Deserialize(str);
        }
        return pNode;
    }
}
